package main

import (
	"container/list"
	"fmt"
)

func main() {
	dailyT := dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76, 73})
	fmt.Println(dailyT)
}

/**
思路：
1. 利用栈来处理，这样不用每个元素都要遍历一次数组
2. 栈为空或者数组元素不大于栈顶元素时，把数组的索引压栈
3. 大于时用索引能很容易计算出天数，并保存到以栈顶为索引的数组，栈顶出栈，重复 2 和 3 的步骤
4. 栈可以用单链表实现，因为只对头元素增加和删除
 */
func dailyTemperatures(T []int) []int {
	result := make([]int, len(T))
	stack := list.New()

	for i := range T {
		front := stack.Front()

		for front != nil && T[i] > T[front.Value.(int)] {
			val := front.Value.(int)

			result[val] = i - val
			stack.Remove(front)

			front = stack.Front()
		}

		stack.PushFront(i)
	}

	return result
}
